package org.example.myleet.p629;

public class Solution {
    /**
     * 思路：动态规划
     * 推导方式，首先考虑从[1]->[1,2]，[1]中只有k=0，数量为1，[1,2]中有k=0，数量为1，k=1，数量为1
     * [1,2]是从[1]加入2在末端得到的，即k=0的前进结果
     * [2,1]是从[1]加入2在1的左侧得到的，即k=0的另一个前进结果，因此是在一直n-1个数的所有k结果基础上推导出加入n之后的所有k情况
     * 对于前n-1个数，考虑新加入n，加入的n会出现在数列1...n-1末尾、n-1左侧、n-2左侧......因此对于n-1各种k的情况将累计到第n个数加入情况的k+1位置上
     * 递推过程中，第n行的k位置累计的情况数为n-1行的[k - (n-1), k]范围内的情况数之和，k - (n-1)是当n在数列1...n-1最左侧时，增加了n-1个逆序对导致
     * 因此要累积n-1行的k - (n-1)位置的计数，k是当n在数列1...n-1最右侧时，没有增加逆序对导致
     * [k - (n-1), k]中间的情况均可能发生，因此都要累积，为了加速这个累积结果的计算，可以考虑前缀和
     */
    public int kInversePairs(int n, int k) {
        int mod = 1000000007;
        long[] kLastArr = new long[1];
        kLastArr[0] = 1;
        for (int i = 2; i <= n; ++i) {
            int newLen = kLastArr.length + i - 1;
            if (newLen > 1001) {
                //我们只要前1001个，满足k=1000的情况就行了，后面的丢弃
                newLen = 1001;
            }
            //下一行，即第n行
            long[] kCurArr = new long[newLen];
            long sum = kLastArr[0];
            kCurArr[0] = sum;
            for (int j = 1; j < kCurArr.length; ++j) {
                //计算前缀和，累积[k - (n-1), k]的数量，不在范围内的要适当加减掉，注意mod的作用
                int outIdx = j - i;
                if (outIdx >= 0) {
                    sum -= kLastArr[outIdx];
                    if (sum < 0) {
                        sum += mod;
                    }
                }
                int inIdx = j;
                if (inIdx < kLastArr.length) {
                    sum += kLastArr[inIdx];
                    if (sum > mod) {
                        sum -= mod;
                    }
                }
                //新的一行赋值
                kCurArr[j] = sum;
            }
            kLastArr = kCurArr;
        }
        if (k >= kLastArr.length) {
            return 0;
        }
        return (int) kLastArr[k];
    }
}
